/*
https://leetcode.cn/problems/frog-position-after-t-seconds/description/
1377. T 秒后青蛙的位置
方钊堉 2024.11.6
dfs
*/

typedef struct Node {
    double probability;
    set<int> next;
    Node() {
        probability = 0;
    }
};

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<Node> nodes(n + 1); // 初始化节点数组
        vector<bool> visited(n + 1, false); // 访问标记数组

        // 构建图的邻接表
        for (const auto& edge : edges) {
            nodes[edge[1]].next.insert(edge[0]);
            nodes[edge[0]].next.insert(edge[1]);
        }

        // 从节点1开始跳，初始概率为1.0
        nodes[1].probability = 1.0;
        dfs(nodes, visited, 1, t, target);
        return nodes[target].probability;
    }

    void dfs(vector<Node>& nodes, vector<bool>& visited, int currentNode, int timeLeft, int target) {
        if (timeLeft <= 0) {
            return; // 时间用完，停止搜索
        }

        visited[currentNode] = true; // 标记当前节点为已访问
        int nextCount = nodes[currentNode].next.size();

        // 如果当前节点不是起点，需要减去父节点
        if (currentNode != 1) {
            --nextCount;
        }

        if (nextCount > 0) {
            if (currentNode == target) {
                // 如果当前节点是目标节点，但还有时间且可以继续跳，则概率为0
                nodes[currentNode].probability = 0;
                return;
            }

            // 遍历当前节点的所有子节点
            for (auto& nextNode : nodes[currentNode].next) {
                if (!visited[nextNode]) {
                    // 计算子节点的概率
                    nodes[nextNode].probability = (1.0 / nextCount) * nodes[currentNode].probability;
                    dfs(nodes, visited, nextNode, timeLeft - 1, target);
                }
            }
        }
    }
};